7.5. Dengeli Ağaç ve AVL Ağaç Yapısı

Dengeli ağaç (balanced tree), gelişmesini tüm dallarına homojen biçimde yansıtan ağaç şeklidir; tanım olarak, herhangi bir düğümüne bağlı altağaçların yükseklikleri arasındaki fark, şekil a) ve b)'de görüldüğü gibi, en fazla 1 (bir) olmalıdır. Bir dalın fazla büyümesi ağacın dengesini bozar ve ağaç üzerine hesaplanmış karmaşıklık hesapları ve yürütme zamanı bağıntılarından sapılır. Dolayısıyla ağaç veri modelinin en önemli getirisi kaybolmaya başlar.

Yapılan istatistiksel çalışmalarda, ağacın oluşturulması için gelen verilerin rastgele olması durumda ağacın dengeli olduğu veya çok az sapma gösterdiği gözlenmiştir [HIBBARD-1962].

Teorem: İkili arama ağacı oluşturulurken düğümlerin yerini belirleyecek olan anahtar sözcüğün rastgele özellikte olması durumunda n düğümlü bir ikili arama ağacının ortalama yüksekliği O(Log₂N ) olur. [İspatı için bkz CORMEN ve ark-1990]

Bir ikili arama ağacı AVL yöntemine gör kurulursa ikili AVL arama ağacı (binary AVL search tree) olarak adlandırılır ve hem ikili arama ağacı hem de AVL ağacı özelliklerini taşır. İkili AVL arama ağaçları üzerinde ekleme, silme ve arama gibi işlemlerin zaman maliyetleri, veriler rastgele özellikte gelmezse bile, O(yükseklik)=O(log₂N) olur.